package b;

import org.junit.Test;
import 其他.DataStructure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
public class 序列化反序列化 {
    @Test
    public void test() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t3.left = t4;
        t3.right = t5;
        /**
         *       1
         *     2   3
         *    n n 4 5
         */
        System.out.println("序列化成->" + serialize(t1));
        TreeNode root = deserialize("1 2 3 n n 4 5 n n n n ");
        System.out.println("->" + serialize(root)); //能解出来就对
    }

    //1,n,n
    String serialize(TreeNode root) {
        if(root==null)return "";//空
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>(); q.add(root);
        //""res不pt
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if(cur==null){
                res.append("n ");
            }else{
                res.append(cur.val+" ");
                q.add(cur.left); q.add(cur.right);
            }
        }
        return res.toString();
    }
    //造树
    TreeNode deserialize(String w){
        if(w=="")return null;//空
        String[] s = w.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(s[0])); int i=1;
        Queue<TreeNode> q = new LinkedList<>(); q.add(root);
        while(i<s.length){
            //队列poll跟踪上一个node
            TreeNode cur = q.poll();
            String L=s[i],R=s[i+1];
            if(!L.equals("n")){
                TreeNode left = new TreeNode(Integer.parseInt(L));
                cur.left=left; q.add(left);
            }
            if(!R.equals("n")){
                TreeNode right = new TreeNode(Integer.parseInt(R));
                cur.right=right; q.add(right);
            }
            //核心：满二叉树放心+2
            i+=2;
        }
        return root;
    }
}
